﻿#region

using Common.DataStructures.Heap;

#endregion

namespace AdvancedTraining.Lesson41;

/// <summary>
/// 魔法到达目标点问题
/// </summary>
/// <remarks>
/// 来自网易互娱
/// N个结点之间，表世界存在双向通行的道路，里世界存在双向通行的传送门。
/// 若走表世界的道路，花费一分钟。
/// 若走里世界的传送门，不花费时间，但是接下来一分钟不能走传送门。
/// 输入： T为测试用例的组数，对于每组数据:
/// 第一行：N M1 M2 N代表结点的个数1到N
/// 接下来M1行 每行两个数，u和v，表示表世界u和v之间存在道路
/// 接下来M2行 每行两个数，u和v，表示里世界u和v之间存在传送门
/// 现在处于1号结点，最终要到达N号结点，求最小的到达时间 保证所有输入均有效，不存在环等情况
///
/// 算法思路：
/// 使用改进的Dijkstra算法，每个城市有两种状态：
/// 0表示上一步是走路到达的，1表示上一步是传送到达的
/// 使用优先队列(小根堆)来扩展状态，每次选择当前时间最小的状态
///
/// 状态转移：
/// 1. 从当前状态(preTransfer, city)出发：
///    - 如果走路，所有相邻城市都可以通过道路到达，时间+1，新状态为(0, next)
///    - 如果当前preTransfer=0（上一步是走路），可以使用传送门，时间不变，新状态为(1, next)
///    - 如果当前preTransfer=1（上一步是传送），不能继续传送，只能走路
///
/// 时间复杂度：O((N+M)logN)，其中N是节点数，M是边数
/// 空间复杂度：O(N)
/// </remarks>
public class MagicGoToAim
{
    /// <summary>
    /// 计算从起点到终点的最短时间
    /// </summary>
    /// <param name="n">节点数量</param>
    /// <param name="roads">道路数组，roads[i]表示从i可以通过道路到达的城市</param>
    /// <param name="gates">传送门数组，gates[i]表示从i可以传送到达的城市</param>
    /// <returns>从0到n-1的最少用时</returns>
    public static int Fast(int n, int[][] roads, int[][] gates)
    {
        // 初始化距离数组，distance[0][i]表示走路到达i的最小时间，distance[1][i]表示传送到达i的最小时间
        var distance = new int[2][];
        distance[0] = new int[n];
        distance[1] = new int[n];

        // 初始化为无穷大
        for (var i = 1; i < n; i++)
        {
            distance[0][i] = int.MaxValue;
            distance[1][i] = int.MaxValue;
        }

        // 小根堆，根据距离排序，距离小的点优先处理
        var heap = new Heap<Node>((a, b) => a.Cost - b.Cost);
        heap.Push(new Node(0, 0, 0));

        // 记录访问状态，visited[0][i]表示已通过走路访问i，visited[1][i]表示已通过传送访问i
        var visited = new bool[2][];
        visited[0] = new bool[n];
        visited[1] = new bool[n];

        while (!heap.isEmpty)
        {
            var cur = heap.Pop();
            if (visited[cur.PreTransfer][cur.City]) continue;
            visited[cur.PreTransfer][cur.City] = true;

            // 走路的方式：所有相邻城市都可以通过道路到达，时间+1，新状态为(0, next)
            foreach (var next in roads[cur.City])
            {
                if (distance[0][next] > cur.Cost + 1)
                {
                    distance[0][next] = cur.Cost + 1;
                    heap.Push(new Node(0, next, distance[0][next]));
                }
            }

            // 传送的方式：只有上一步是走路的状态才能使用传送门，时间不变，新状态为(1, next)
            if (cur.PreTransfer == 0)
            {
                foreach (var next in gates[cur.City])
                {
                    if (distance[1][next] > cur.Cost)
                    {
                        distance[1][next] = cur.Cost;
                        heap.Push(new Node(1, next, distance[1][next]));
                    }
                }
            }
        }

        // 返回到达终点N-1的最小时间（可能是走路到达也可能是传送到达）
        return Math.Min(distance[0][n - 1], distance[1][n - 1]);
    }

    /// <summary>
    /// 节点类，表示状态
    /// </summary>
    public class Node
    {
        /// <summary>
        /// 上一步是否是传送（0=走路，1=传送）
        /// </summary>
        public readonly int PreTransfer;

        /// <summary>
        /// 当前城市编号
        /// </summary>
        public readonly int City;

        /// <summary>
        /// 到达当前城市的总时间
        /// </summary>
        public readonly int Cost;

        public Node(int preTransfer, int city, int cost)
        {
            PreTransfer = preTransfer;
            City = city;
            Cost = cost;
        }
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== MagicGoToAim 测试 ===");

        // 测试用例1：简单情况 - 只有道路
        var roads1 = new int[][] { new[] { 1 }, new[] { 0, 2 }, new[] { 1 } };
        var gates1 = new int[][] { new int[0], new int[0], new int[0] };
        Console.WriteLine("测试1 - 只有道路:");
        Console.WriteLine($"输入: 3个节点，0->1->2");
        Console.WriteLine($"结果: {Fast(3, roads1, gates1)} (期望: 2)");
        Console.WriteLine();

        // 测试用例2：有传送门可以加速
        var roads2 = new int[][] { new[] { 1 }, new[] { 0, 2 }, new[] { 1 } };
        var gates2 = new int[][] { new[] { 2 }, new int[0], new int[0] };
        Console.WriteLine("测试2 - 有传送门加速:");
        Console.WriteLine($"输入: 3个节点，0可以直接传送到2");
        Console.WriteLine($"结果: {Fast(3, roads2, gates2)} (期望: 0)");
        Console.WriteLine();

        // 测试用例3：传送门和道路混合
        var roads3 = new int[][] { new[] { 1 }, new[] { 0, 2 }, new[] { 1, 3 }, new[] { 2 } };
        var gates3 = new int[][] { new[] { 2 }, new[] { 3 }, new int[0], new int[0] };
        Console.WriteLine("测试3 - 传送门和道路混合:");
        Console.WriteLine($"输入: 4个节点，0->2传送，1->3传送");
        Console.WriteLine($"结果: {Fast(4, roads3, gates3)} (期望: 1)");
        Console.WriteLine();

        // 测试用例4：复杂网络
        var roads4 = new int[][]
        {
            new[] { 1, 2 },
            new[] { 0, 2, 3 },
            new[] { 0, 1, 3, 4 },
            new[] { 1, 2, 4 },
            new[] { 2, 3 }
        };
        var gates4 = new int[][]
        {
            new[] { 3 },
            new[] { 4 },
            new[] { 0 },
            new int[0],
            new int[0]
        };
        Console.WriteLine("测试4 - 复杂网络:");
        Console.WriteLine($"输入: 5个节点的复杂网络");
        Console.WriteLine($"结果: {Fast(5, roads4, gates4)} (期望: 1)");
        Console.WriteLine();

        // 测试用例5：只能走路的路径
        var roads5 = new int[][] { new[] { 1 }, new[] { 0, 2 }, new[] { 1, 3 }, new[] { 2, 4 }, new[] { 3 } };
        var gates5 = new int[][] { new int[0], new int[0], new int[0], new int[0], new int[0] };
        Console.WriteLine("测试5 - 只能走路的路径:");
        Console.WriteLine($"输入: 5个节点，线性路径");
        Console.WriteLine($"结果: {Fast(5, roads5, gates5)} (期望: 4)");
        Console.WriteLine();

        // 测试用例6：直接传送
        var roads6 = new int[][] { new[] { 1 }, new[] { 0, 2 }, new[] { 1 } };
        var gates6 = new int[][] { new[] { 2 }, new int[0], new int[0] };
        Console.WriteLine("测试6 - 直接传送:");
        Console.WriteLine($"输入: 3个节点，0->2传送");
        Console.WriteLine($"结果: {Fast(3, roads6, gates6)} (期望: 0)");
        Console.WriteLine();

        Console.WriteLine("=== 测试完成 ===");
        Console.WriteLine();
        Console.WriteLine("算法说明:");
        Console.WriteLine("- 状态(0, i): 通过走路到达节点i的最小时间");
        Console.WriteLine("- 状态(1, i): 通过传送到达节点i的最小时间");
        Console.WriteLine("- 传送限制：只有上一步是走路的状态才能使用传送门");
        Console.WriteLine("- 时间计算：走路花费1分钟，传送花费0分钟");
    }
}